Existing terrain level-of-detail (LOD) algorithms use a hierarchy of mesh refinement operations to adapt the surface tessellation. These algorithms can be categorized by the structure of these hierarchies.
For example, irregular meshes such as triangulated irregular networks provide a good approximation of a terrain for a given number of triangle faces, but require the tracking of mesh adjacencies and refinement dependencies. Some hierarchies use Delaunay triangulations (see e.g., Cohen-Or, D. et al., Temporal Continuity of Levels of Detail in Delaunay Triangulated Terrain, IEEE Visualization 1996, 37-42; Cignoni, P. et al., Representation and Visualization of Terrain Surfaces at Variable Resolution, The Visual Computer 13(5), 199-217, 1997; Rabinovich, B. et al, Visualization of Large Terrains in Resource-Limited Computing Environments, IEEE Visualization 1997), while others allow arbitrary connectivities (see e.g., De Floriana E. et al., Building and Traversing a Surface at Variable Resolution, IEEE Visualization 1997, 103-110; Hoppe, H., Optimization of Mesh Locality for Transparent Vertex Caching, ACM SIG-GRAPH 1999, 269-276; El-Sans, J., et al., Generalized View-Dependent Simplification, Proceedings of Eurographics, 1999, 83-94).
Bin-tree hierarchies such as longest-edge bisection, restricted quadtrees, and hierarchies of right triangles use the recursive bisection of right triangles to simplify memory layout and traversal algorithms. However, these semi-regular meshes still involve pointer-based data structures and immediate-mode rendering (see e.g., Lindstrom, P. et al., Real-Time, Continuous Level of Detail Rendering of Height Fields, ACM SIGGRAPH 1996, 109-118; Duchaineau, M. et al., Roaming Terrain: Real-time Optimally Adapting Meshes, IEEE Visualization 1997, 81-88; Pajarola, R., Large Scale Terrain Visualization Using the Restricted Quadtree Triangulation, IEEE Visualization 1998, 19-26; Rottger, S. et al., Real-time Generation of Continuous Levels of Detail for Height Fields, Central Europe Conf. on Computer Graphics and Vis., 315-322; and Blow, J., Terrain Rendering at High Levels of Detail, Game Developers Conference 2000).
Further, Bin-tree regions define coarser-grain refinement operations on regions associated with a bin-tree structure, and pre-computed triangulated regions are uploaded to buffers cached in video memory, thereby boosting rendering throughput. However, caching hinders use of geomorphs for temporal coherence. See e.g., Levenberg, J., et al., Fast View-dependent Level-of-Detail Rendering Using Cached Geometry, IEEE Visualization 2002, 259-266; Cignoni, P. et al., BDAM—Batched Dynamic Adaptive Meshes for High Performance Terrain Visualization, Computer Graphics Forum 22(3) 2003; Cignoni, P. et al., Planet-sized Batched Dynamic Adaptive Meshes (P-BDAM), IEEE Visualization 2003. Many other methods have been proposed for view dependent mapping. See e.g., Bishop, L., et al., Designing a PC Game Engine, IEEE CG&A 18(1), 46-53 1998; De Boer, W., Fast Terrain Rendering Using Geometrical Mipmapping, http://www.flipcode.com/tutorials/geomipmaps.pdf, dated October 2000; Wagner, D., 2004, Terrain Geomorphing in the Vertex Shader, In ShaderX2: Shader Programming Tips & Tricks with DirectX 9, Wordware Publishing 2004; Gumhold, S. et al., Multiresolution Rendering with Displacement Mapping, Graphics Hardware Workshop 1999; Dogget, M. et al., Adaptive View-dependent Tessellation of Displacement Maps, Graphics Hardware Workshop, 2000; Moule, K. et al., Efficient Bounded Adaptive Tessellation of Displacement Maps, Graphics Interface, 2002. Other methods have been proposed for texture maps. See e.g., Doilner, J. et al., Texturing Techniques for Terrain visualization, IEEE Visualization 2000, 227-234; Tanner, C. et al., The Clipmap: A Virtual Mipmap, ACM SIG-GRAPH 1998, 151-158 (“Tanner 1998”).